package com.hellohu.dp;

import org.assertj.core.api.Assertions;
import org.junit.Test;

public class ShortestPath {

    @Test
    public void test() {
        Assertions
                .assertThat(dpSolution(new int[][] { { 1, 3, 5, 9 }, { 2, 1, 3, 4 }, { 5, 2, 6, 7 }, { 6, 8, 4, 3 }, }))
                .isEqualTo(19);
        Assertions.assertThat(
                violenceSolution(new int[][] { { 1, 3, 5, 9 }, { 2, 1, 3, 4 }, { 5, 2, 6, 7 }, { 6, 8, 4, 3 }, }))
                .isEqualTo(19);
    }

    public int dpSolution(int[][] w) {
        int m = w.length;
        int n = w[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = w[0][0];

        for (int i = 1; i < m; ++i) {
            dp[0][i] = dp[0][i - 1] + w[0][i];
        }
        for (int i = 1; i < n; ++i) {
            dp[i][0] = dp[i - 1][0] + w[i][0];
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + w[i][j];
            }
        }
        return dp[m - 1][n - 1];
    }

    public int violenceSolution(int[][] w) {
        return violenceSolution(w, 0, 0, w[0][0]);
    }

    /**
     * 暴力求最短路径
     * 
     * @param w
     * @param i
     * @param j
     * @param cur 当前累计值
     * @return
     */
    public int violenceSolution(int[][] w, int i, int j, int cur) {
        if (i == w.length - 1 && j == w[0].length - 1) {
            return cur;
        }
        if (i == w.length - 1) {
            // 只能向右
            return violenceSolution(w, i, j + 1, cur + w[i][j + 1]);
        } else if (j == w[0].length - 1) {
            // 只能向下
            return violenceSolution(w, i + 1, j, cur + w[i + 1][j]);
        } else {
            // 能下能右
            return Math.min(violenceSolution(w, i, j + 1, cur + w[i][j + 1]),
                    violenceSolution(w, i + 1, j, cur + w[i + 1][j]));
        }
    }
}
